package org.example;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

@Slf4j
public class Search {

    @Test
    void binarySearch() {
        int[] array = IntStream.range(0, 20).toArray();

        int target = 20;
        int idx = -1;

        for (int i = 0, j = array.length - 1; i <= j; ) {
            int mid = (i + j) / 2;
            int v = array[mid];
            if (v == target) {
                idx = i;
                break;
            }

            if (target < v) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        System.out.println(idx);
    }

    @Test
    void binarySearch4Insert() {
        int[] array = {1, 3, 6, 8, 12, 15, 23, 26, 31, 35};

        int target = 2;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            int v = array[mid];
            if (v == target) {
                break;
            }

            if (target < v) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        System.out.println(i);
    }

    @Test
    void binarySearch4InsertV2() {
        int[] array = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};

        int target = 6;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            if (target > array[mid]) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }

        System.out.println(i);
    }

    @Test
    void binarySearchLeftEdge() {
        int[] array = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};

        int target = 6;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            if (target > array[mid]) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }

        if (array[i] == target) {
            System.out.println(i);
        } else {
            System.out.println(-1);
        }
    }



    @Test
    void binarySearchLeftEdgeV2() {
        int[] array = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};
        int target = 6;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            int midV = array[mid];
            if (target - 0.5 <= midV) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        System.out.println(i);
    }

    @Test
    void binarySearchRightEdge() {
        int[] array = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};

        int target = 6;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            if (target < array[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        if (array[j] == target) {
            System.out.println(j);
        } else {
            System.out.println(-1);
        }
    }

    @Test
    void binarySearchRightEdgeV2() {
        int[] array = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};

        int target = 6;
        int i = 0, j = array.length - 1;
        for (; i <= j; ) {
            int mid = (i + j) / 2;
            if (target + 0.5 < array[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        System.out.println(j);
    }

    @Test
    void twoSumHashTable() {
        int[] arrays = {2, 7, 11, 15};
        int target = 13;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arrays.length; i++) {
            map.put(arrays[i], i);
        }


        for (int i = 0; i < arrays.length; i++) {
            int num = arrays[i];
            if (map.containsKey(target - num)) {
                log.info("{} + {} = {}", i, map.get(target - num), target);
                break;
            }
        }

    }
}
